We study convergence of the iterative projected gradient (IPG) algorithm forarbitrary (possibly nonconvex) sets and when both the gradient and projectionoracles are computed approximately. We consider different notions ofapproximation of which we show that the Progressive Fixed Precision (PFP) andthe $(1+\epsilon)$-optimal oracles can achieve the same accuracy as for theexact IPG algorithm. We show that the former scheme is also able to maintainthe (linear) rate of convergence of the exact algorithm, under the sameembedding assumption. In contrast, the $(1+\epsilon)$-approximate oraclerequires a stronger embedding condition, moderate compression ratios and ittypically slows down the convergence. We apply our results to acceleratesolving a class of data driven compressed sensing problems, where we replaceiterative exhaustive searches over large datasets by fast approximate nearestneighbour search strategies based on the cover tree data structure. Fordatasets with low intrinsic dimensions our proposed algorithm achieves acomplexity logarithmic in terms of the dataset population as opposed to thelinear complexity of a brute force search. By running several numericalexperiments we conclude similar observations as predicted by our theoreticalanalysis.
展开▼
